Converting graph U to different representations

  • The edge list representation simply enumerates all edges as pairs of vertices: {A–B, A–C, B–D}. This is the most compact and straightforward way to describe the graph structure, requiring only O(m) space where m is the number of edges.
  • The adjacency list representation stores for each vertex a set of its neighbors. For undirected graphs, we must maintain symmetry: if B is in A's list, then A must be in B's list. This gives us A:{B,C}, B:{A,D}, C:{A}, D:{B}.
  • When converting from edge list to adjacency list, we iterate through each edge and add the appropriate entries to both endpoints' neighbor sets. This symmetry check is critical for undirected graphs to ensure consistency in all operations.
  • Both representations have trade-offs: the edge list is simple but slow for adjacency queries (O(m)), while the adjacency list uses slightly more space O(n+m) but enables fast neighbor iteration and near-constant-time adjacency tests when using hash sets.